struct VCCTarjan{ // 点双连通分量

using weight_t = int;
using vi = vector<int>;

struct edge_t{
    int from;
    int to;
    weight_t w;
    edge_t(int a, int b, weight_t c):from(a),to(b),w(c){}
};

int N;
vector<edge_t> Edges;
vector<vi> G; // 编号从1开始

/// 点数和边数
void init(int n, int m){
    G.assign((N = n) + 1, {});
    Edges.clear();
    Edges.reserve(m + m); // 无向边
    return;
}

/// 双向边
void mkBiEdge(int a, int b, weight_t w=0){
    G[a].emplace_back(Edges.size());
    Edges.emplace_back(a, b, w);
    G[b].emplace_back(Edges.size());
    Edges.emplace_back(b, a, w);
    return;
}

/// 主函数
void Tarjan(){
    /// 初始化
    Dfn.assign(N + 1, 0);
    Low.assign(N + 1, 0);
    Stack.assign(Edges.size(), 0);
    Belong2VCC.assign(Edges.size(), 0);
    IsVisited.assign(Edges.size(), 0);
    Represent.assign(Edges.size(), 0);
    TimeStamp = VCCCnt = StackTop = 0;

    for(int i=1;i<=N;++i)if(0 == Dfn[i])dfs(i, i);
    return;
}

void dfs(int u, int pre){
    Dfn[u] = Low[u] = ++TimeStamp;

    int v, j;
    for(auto i : G[u])if(not IsVisited[i]){
        IsVisited[i] = IsVisited[i ^ 1] = true;

        if(0 == Dfn[v = Edges[i].to]){ // 入栈
            Stack[StackTop++] = i;
            dfs(v, u);
            if(Low[v] < Low[u]) Low[u] = Low[v];

            /// 说明u是割点，栈内的边属于同一个点双
            if(Dfn[u] <= Low[v]){
                Represent[Belong2VCC[i] = Belong2VCC[i ^ 1] = ++VCCCnt] = i;
                while((j = Stack[--StackTop]) != i){
                    Belong2VCC[j] = Belong2VCC[j ^ 1] = VCCCnt;
                    Represent[VCCCnt] = min(j, Represent[VCCCnt]);
                }
            }
        }else if(v != pre and Dfn[v] < Dfn[u]){
            Low[u] = min(Low[u], Dfn[v]);
            Stack[StackTop++] = i;
        }
    }
}

int StackTop;
vi Stack; // 辅助栈
int TimeStamp;
vi Dfn, Low;
/// 对点而言，割点可能属于多个点双连通分量
/// 编号使用的是内部编号
/// 实际读入边的顺序记作1,2,3,...，分别对应内部编号(0,1)(2,3)(4,5)...
vi Belong2VCC; // 边i属于第Bi个点双连通分量，从1开始
vi Represent; // Ri表示第i个点双中最小的边的编号
int VCCCnt; // 点双的数量
vi IsVisited;

};